We introduce two cheater identifiable secret sharing (CISS) schemes with efficient reconstruction, tolerating t

Many researchers studied computationally-secure (verifiable) secret sharing schemes which distribute multiple secrets with a bulletin board. However, the security definition is ambiguous in many of the past articles. In this paper, we first review existing schemes based on formal definitions of indistinguishability of secrets, verifiability of consistency, and cheater-detectability. And then, we propose a new secret sharing scheme which is the first scheme with indistinguishability of secrets, verifiability, and cheater-detectability, and allows to share secrets with arbitrary access structures. Further, our scheme is provably secure under well known computational assumptions.

Secret sharing is a method of information protection for security. The information is divided into n shares and reconstructed from any k shares, but no knowledge of the information is revealed from k-1 shares. Physical layer security is a method of achieving favorable reception conditions at the destination terminal in wireless communications. In this study, we propose a security enhancement technique for wireless packet communications. The technique uses secret sharing and physical layer security to exchange a secret encryption key. The encryption key for packet information is set as the secret information in secret sharing, and the secret information is divided into n shares. Each share is located in the packet header. The base station transmits the packets to the destination terminal by using physical layer security based on precoded multi-antenna transmission. With this transmission scheme, the destination terminal can receive more than k shares without error and perfectly recover the secret information. In addition, an eavesdropper terminal can receive less than k-1 shares without error and recover no secret information. In this paper, we propose a protection technique using secret sharing based on systematic Reed-Solomon codes. The technique establishes an advantageous condition for the destination terminal to recover the secret information. The evaluation results by numerical analysis and computer simulation show the validity of the proposed technique.

In this paper, we construct ideal and probabilistic secret sharing schemes for some multipartite access structures, including the General Hierarchical Access Structure and Compartmented Access Structures. We devise an ideal scheme which implements the general hierarchical access structure. For the compartmented access structures, we consider three special access structures. We propose ideal and probabilistic schemes for these three compartmented access structures by bivariate interpolation.

A threshold secret sharing scheme can realize reliable delivery of important content using redundant routes through a network. Furthermore, multicast delivery of threshold secret shared content can achieve efficient resource utilization thanks to the application of multicast and network coding techniques to multiple pieces of the content. Nevertheless, a tradeoff exists between reliability and efficiency if multicast content delivery uses network coding. This paper proposes a flexible multicast delivery scheme for threshold secret shared content that can control the tradeoff between reliability and efficiency. The proposed scheme classifies all the pieces obtained from the original content into multiple groups, and each group is subjected to network coding independently. An optimization procedure is proposed for the multicast delivery scheme, which involves two different heuristic delivery route computation methods applicable to large-scale networks. Evaluation results show that the optimized multicast delivery scheme adopting an appropriate grouping method and classifying the pieces into a suitable number of groups can minimize the required link bandwidth while satisfying a specified content loss probability requirement.

Harn and Lin proposed an algorithm to detect and identify cheaters in Shamir's secret sharing scheme in the journal Designs, Codes and Cryptography, 2009. In particular, their algorithm for cheater identification is inefficient. We point out that some of their conditions for cheater detection and identification essentially follow from those on error detection/correction of Reed-Solomon codes, which have efficient decoding algorithms, while some other presented conditions turn out to be incorrect. The extended and improved version of the above mentioned scheme was recently presented at the conference International Computer Symposium 2012 (and the journal version appeared in the journal IET Information Security). The new scheme, which is ideal (i.e. the share size is equal to that of the secret), attempts to identify cheaters from minimal number of shares (i.e. the threshold of them). We show that the proposed cheater identification is impossible using the arguments from coding theory.

We introduce a coding theoretic criterion for Yamamoto's strong security of the ramp secret sharing scheme. After that, by using it, we show the strong security of the strongly multiplicative ramp secret sharing proposed by Chen et al. in 2008.

A secret sharing scheme is said to be d-multiplicative if the scheme allows the players to multiply shared d secrets by locally converting their shares into an additive sharing of the product. In the previous work, the following negative result for perfect secret sharing has been shown: The d-multiplicative secret sharing for d players is impossible. This paper extends the impossibility result to non-perfect secret sharing. Our main result is a proof that d-multiplicative secret sharing for d players is impossible even if every player has partial information on the secret (e.g., all but one bit). This result means that there is no need to relax the privacy requirement with leakage of partial information only for the purpose of d-multiplication.

A threshold secret sharing scheme protects content by dividing it into many pieces and distributing them among different servers. This scheme can also be utilized for the reliable delivery of important content. Thanks to this scheme, the receiver can still reconstruct the original content even if several pieces are lost during delivery due to a multiple-link failure. Nevertheless, the receiver cannot reconstruct the original content unless it receives pieces more than or equal to the threshold. This paper aims to obtain reliable delivery routes for the pieces, as this will minimize the probability that the receiver cannot reconstruct the original content. Although such a route optimization problem can be formulated using an integer linear programming (ILP) model, computation of globally optimum delivery routes based on the ILP model requires large amounts of computational resources. Thus, this paper proposes a lightweight method for computing suboptimum delivery routes. The proposed greedy method computes each of the delivery routes successively by using the conventional shortest route algorithm repeatedly. The link distances are adjusted iteratively on the basis of the given probability of failure on each link and they are utilized for the calculation of each shortest route. The results of a performance evaluation show that the proposed method can compute sub-optimum delivery routes efficiently thanks to the precise adjustment of the link distances, even in backbone networks on a real-world scale.

Secret sharing (SS) has been extensively studied as for both secure data storage and a fundamental building block for multiparty computation (MPC). Recently, Kikuchi et al. proposed a passively and unconditionally secure conversion protocol that converts from a share of a ramp scheme to another of homomorphic SS scheme. The share-size of the ramp scheme is small, and the homomorphic SS scheme is a class of SS schemes that includes Shamir's and replicated SS schemes, which are convenient for MPC. Therefore, their protocol is a conversion from an SS scheme whose share-size is small to MPC-friendly SS schemes, and can be applied to reduce the amount of data storage while maintaining extendibility to MPC. We propose five unconditionally and actively secure protocols in the honest majority. In this paper, we consider a privacy and correctness as security requirement and does not consider a robustness: A cheat caused by an active adversary must be detected. These protocols consist of two conversion protocols, two reveal protocols and a protocol generating specific randomness. Main protocols among them are two conversion protocols for bilateral conversion between a ramp scheme and linear SS scheme, and the others are building blocks of the main protocols. Linear SS scheme is a subset of homomorphic SS scheme but includes both Shamir's and replicated SS schemes. Therefore, these main protocols are conversions between an SS scheme whose share-size is small to MPC-friendly SS schemes. These main protocols are unconditionally and actively secure so if MPC protocols used after the conversion are actively secure, the whole system involving SS scheme, conversion, and MPC protocols can be unconditionally and actively secure by using our main protocols. One of our two main protocols is the first to convert from MPC-friendly SS schemes to the ramp scheme. This enhances applications, such as secure backup, of the conversion protocol. Other than the two main protocols, we propose a protocol for generating specific randomnesses and two reveal protocols as building blocks. The latter two reveal protocols are actively and unconditionally secure in the honest majority and requires O(n||F||)-bit communication per revealing, and we believe that it is independently interest.

We introduce a graphical calculus for multi-qutrit systems (the qutrit ZX-calculus) based on the framework of dagger symmetric monoidal categories. This graphical calculus consists of generators for building diagrams and rules for transforming diagrams, which is obviously different from the qubit ZX-calculus. As an application of the qutrit ZX-calculus, we give a graphical description of a (2, 3) threshold quantum secret sharing scheme. In this way, we prove the correctness of the secret sharing scheme in a intuitively clear manner instead of complicated linear algebraic operations.

Password-protected secret sharing (PPSS, for short) schemes were proposed by Bagherzandi, Jarecki, Saxena and Lu. In this paper, we consider another attack for PPSS schemes which is based on public parameters and documents. We show that the protocol proposed by Bagherzandi et al. is broken with the attack. We then propose an enhanced protocol which is secure against the attack.

Secret sharing scheme (SS) has been extensively studied since SSs are important not only for secure data storage but also as a fundamental building block for multiparty computation (MPC). For an application to secure data storage, the share size of SS is an important factor. For an application to a building block for MPC, the extendibility to MPC is needed. Computationally secure SSs and a ramp scheme have a small share size but there have been few studies concerning their MPC. In contrast, there have been many studies about MPC on Shamir's and replicated SSs while their share size is large. We consider an application scenario of SS such as applying SSs to secure data storage service with MPC. In this application, users store their data in servers through SS, and sometimes the servers perform MPC as an optional feature. In this case, the extendibility to MPC is needed and good code-efficiency is preferable. We propose a new computational SS, and show how to convert shares of our SS and a ramp SS to those of multiparty-friendly SS such as Shamir's and replicated SS. This enables one to secretly-share data compactly and extend secretly-shared data to MPC if needed.

In secret sharing scheme, Tompa and Woll considered a problem of cheaters who try to make another participant reconstruct an invalid secret. Later, some models of such cheating were formalized and lower bounds of the size of shares were shown in the situation of fixing the minimum successful cheating probability. Under the assumption that cheaters do not know the distributed secret, no efficient scheme is known which can distribute bit strings. In this paper, we propose an efficient scheme for distributing bit strings with an arbitrary access structure. When distributing a random bit string with threshold access structures, the bit length of shares in the proposed scheme is only a few bits longer than the lower bound.

In this paper, we present a construction of (n,k,d,m) secure regenerating codes for distributed storage systems against eavesdroppers that can observe either data stored in at most m storage nodes or downloaded data for repairing at most m failed nodes in a network where m < k ≤ d ≤ n-1. The (n,k,d,m) secure regenerating code is based on an (n,k,d) minimum bandwidth regenerating (MBR) code, which was proposed by Rashmi, Shah and Kumar as optimal exact-regenerating codes, for all values of the parameters (n,k,d). The (n,k,d,m) secure regenerating codes have the security as a secret sharing scheme such that even if an eavesdropper knows either data stored in at most m storage nodes or downloaded data for repairing at most m failed nodes, no information about data leaks to the eavesdropper.

Secret sharing schemes have been proposed to protect content by dividing it into many pieces securely and distributing them over different locations. Secret sharing schemes can also be used for the secure delivery of content. The original content cannot be reconstructed by the attacker if the attacker cannot eavesdrop on all the pieces delivered from multiple content servers. This paper aims to obtain secure delivery routes for the pieces, which minimizes the probability that all the pieces can be stolen on the links composing the delivery routes. Although such a route optimization problem can be formulated using an ILP (Integer Linear Programming) model, optimum route computation based on the ILP model requires large amounts of computational resources. Thus, this paper proposes a lightweight route computation method for obtaining suboptimum delivery routes that achieve a sufficiently small probability of all the pieces being stolen. The proposed method computes the delivery routes successively by using the conventional shortest route algorithm repeatedly. The distance of the links accommodating the routes that have already been calculated is adjusted iteratively and utilized for calculation of the new shortest route. The results of a performance evaluation clarify that sufficiently optimum routes can be computed instantly even in practical large-scale networks by the proposed method, which adjusts the link distance strictly based on the risk level at the considered link.

This paper precisely characterizes secret sharing schemes based on arbitrary linear codes by using the relative dimension/length profile (RDLP) and the relative generalized Hamming weight (RGHW). We first describe the equivocation Δm of the secret vector =[s1,...,sl] given m shares in terms of the RDLP of linear codes. We also characterize two thresholds t1 and t2 in the secret sharing schemes by the RGHW of linear codes. One shows that any set of at most t1 shares leaks no information about , and the other shows that any set of at least t2 shares uniquely determines . It is clarified that both characterizations for t1 and t2 are better than Chen et al.'s ones derived by the regular minimum Hamming weight. Moreover, this paper characterizes the strong security in secret sharing schemes based on linear codes, by generalizing the definition of strongly-secure threshold ramp schemes. We define a secret sharing scheme achieving the α-strong security as the one such that the mutual information between any r elements of (s1,...,sl) and any α-r+1 shares is always zero. Then, it is clarified that secret sharing schemes based on linear codes can always achieve the α-strong security where the value α is precisely characterized by the RGHW.

It is becoming more and more important to make use of personal or classified information while keeping it confidential. A promising tool for meeting this challenge is secure multi-party computation (MPC). It enables multiple parties, each given a snippet of a secret s, to compute a function f(s) by communicating with each other without revealing s. However, one of the biggest problems with MPC is that it requires a vast amount of communication. Much research has gone into making each protocol (equality testing, interval testing, etc.) more efficient. In this work, we make a set of multiple protocols more efficient by transforming them into their equivalent batch processing form and propose two protocols: “Batch Logical OR” and “Batch Logical AND.” Using proposed protocols recursively, we also propose “Batch Logical OR-AND” and “Batch Logical AND-OR,” and show arbitrary formula consisting of Boolean protocols, OR gates, and AND gates can be batched. Existing logical OR and logical AND protocols consisting of t equality testing invocations have a communication complexity of O(t), where is the bit length of the secrets. Our batched versions of these protocols reduce it to O( + t). For t interval testing invocations, they reduce both communication and round complexity. Thus they can make the queries on a secret shared database more efficient. For example, the use of the proposed protocols reduces the communication complexity for a query consisting of equality testing and interval testing by approximately 70% compared to the use of the corresponding existing protocols. The concept of the proposed protocols is versatile and can be applied to logical formulae consisting of protocols other than equality testing and interval testing, thereby making them more efficient as well.

An important concept in secret sharing scheme is the access structure. However, determining the access structure of the secret sharing scheme based on a linear code is a very difficult problem. In this work, we provide a method to construct a class of two-weight linear codes over finite rings. Based on the two-weight codes, we present an access structure of a secret sharing scheme.

Group key establishment is an important mechanism to construct a common session key for group communications. Conventional group key establishment protocols use an on-line trusted key generation center (KGC) to transfer the group key for each participant in each session. However, this approach requires that a trusted server be set up, and it incurs communication overhead costs. In this article, we address some security problems and drawbacks associated with existing group key establishment protocols. Besides, we use the concept of secret sharing scheme to propose a secure key transfer protocol to exclude impersonators from accessing the group communication. Our protocol can resist potential attacks and also reduce the overhead of system implementation. In addition, comparisons of the security analysis and functionality of our proposed protocol with some recent protocols are included in this article.